10272. Уменьшите до одного

 

Рассмотрим список целых чисел L. Сначала L содержит целые числа от 1 до n, каждое ровно один раз (но позже может содержать несколько копий некоторых целых чисел). Порядок элементов в L не важен. Вам следует выполнить следующую операцию n – 1 раз:

·        Выберите два элемента из списка, пусть это будут x и y. Они могут быть равными.

·        Удалите выбранные элементы из L.

·        Добавьте число x + y + x * y в L.

В конце L содержит ровно одно целое число. Найдите максимально возможное значение этого целого числа. Поскольку ответ может быть большим, вычислите его по модулю 109 + 7.

 

Вход. Первая строка содержит количество тестов t. Каждая из следующих t строк содержит одно целое число n (1 ≤ n ≤ 106).

 

Выход. Для каждого теста выведите одно целое число – максимальное возможное значение последнего числа в списке, вычисленное по модулю 109 + 7.

 

Пример входа

Пример выхода

3

1

2

4

1

5

119

 

 

РЕШЕНИЕ

математика

 

Анализ алгоритма

Преобразуем выражение:

x + y + x * y = y * (x + 1) + (x + 1) – 1 = (x + 1) * (y + 1) – 1

Удалив из списка числа x и y, вставлено будет (x + 1) * (y + 1) – 1.

Если далее удалить из списка (x + 1) * (y + 1) – 1 и z, то вставлено будет

((x + 1) * (y + 1) – 1 + 1) * (z + 1) – 1 =

(x + 1) * (y + 1) * (z + 1) – 1

Следуя по аналогии, можно утверждать что если изначально

L = {a1, a2, …, an},

то в конце останется число (a1 + 1) * (a2 + 1) * … * (an + 1) – 1.

Поскольку изначально L содержит целые числа от 1 до n, то в конце останется число (1 + 1) * (2 + 1) * … * (n + 1) – 1 = (n + 1)! – 1.

 

Реализация алгоритма

Объявим константы.

 

#define MOD 1000000007

#define MAX 1000002

 

Входные данные содержат несколько тестов. Объявим массив p такой что p[i] = i!.

 

long long p[MAX];

 

Читаем количество тестов tests. Вычисляем факториалы чисел, сохраняем p[i] = i!

 

scanf("%d", &tests);

p[1] = 1;

for (i = 2; i < MAX; i++)

  p[i] = (p[i - 1] * i) % MOD;

 

Обрабатываем тесты. Для каждого входного значения n выводим (n + 1)! – 1.

 

while (tests--)

{

  scanf("%d", &n);

  printf("%lld\n", p[n + 1] - 1);

}

 

Python реализация

Объявим константы.

 

MOD = 1000000007

MAX = 1000002

 

Вычисляем факториалы чисел, сохраняем p[i] = i!

 

p = [1] * MAX

for i in range(2, MAX):

  p[i] = (p[i - 1] * i) % MOD

 

Читаем количество тестов tests.

 

tests = int(input())

 

Обрабатываем тесты. Для каждого входного значения n выводим (n + 1)! – 1.

 

for _ in range(tests):

  n = int(input())

  print(p[n + 1] - 1)